// https://leetcode-cn.com/problems/4sum/
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
		int len = nums.size();
		vector<vector<int>> res;
		if(len < 4){
			return {};
		}
		sort(nums.begin(), nums.end());
		for(auto num : nums){
			cout << num << " ";
		}
		cout << endl;
		
		for(int i = 0; i < len - 3; i++){
			int lleft = i; 
			int rright = len - 1;
			if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
				return res;
			}
			if (nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) {
				continue;
			}
			while(lleft < rright){
				int sum1 = nums[lleft] + nums[rright];
				int tar1 = target-sum1;
				int left = lleft+1;
				int right = rright-1;
				while(left < right){
					if(nums[left] + nums[right] == tar1){
						int find = 0;
						for(auto v : res){
							if(v[0] == nums[lleft] && v[1] == nums[left] && v[2] == nums[right]){
								find = 1;
								break;
							}
						}
						if(find == 0){
							res.push_back({nums[lleft], nums[left], nums[right], nums[rright]});
						}
					}
					if(nums[left] + nums[right] < tar1){
						left++;
						continue;
					} else {
						right--;
						continue;
					}
					// 这里和上面的代码不能合并
					if(nums[left] == nums[left+1]){
						left++;
						continue;
					} else {
						right--;
						continue;
					}
				}
				rright--;
			}
		}
		return res;
    }
	
	// 暴力解法也是可以的，内存占用少，但是耗时很多
	/*
	执行用时：88 ms, 在所有 C++ 提交中击败了55.35%的用户
	内存消耗：12.6 MB, 在所有 C++ 提交中击败了92.40%的用户
	通过测试用例：
	289 / 289
	*/
	vector<vector<int>> fourSum1(vector<int>& nums, int target){
		int len = nums.size();
		vector<vector<int>> res;
		if(len < 4){
			return {};
		}
		sort(nums.begin(), nums.end());
		// for(auto num : nums){
			// cout << num << " ";
		// }
		// cout << endl;
		for(int i = 0; i < len - 3; i++){
			if((long)nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target){
				return res;
			}
			if((long)nums[len-3] + nums[len-3] + nums[len-2] + nums[len-1] < target){
				return res;
			}
			for(int j = i + 1; j < len - 2; j++){
				if((long)nums[i] + nums[len-3] + nums[len-2] + nums[len-1] < target){
					break;
				}
				if((long)nums[i] + nums[j] + nums[j+1] + nums[j+2] > target){
					break;
				}
				for(int k = j + 1; k < len - 1; k++){
					if((long)nums[i] + nums[j] + nums[len-2] + nums[len-1] < target){
						break;
					}
					if((long)nums[i] + nums[j] + nums[k] + nums[k+1] > target){
						break;
					}
					for(int l = k + 1; l < len; l++){
						if((long)nums[i] + nums[j] + nums[k] + nums[l] == target){
							// cout << " j:" << j << ", k:" << k <<", l:" << l << endl;
							res.push_back({nums[i], nums[j], nums[k], nums[l]});
						}
						while(l < len-1 && nums[l] == nums[l+1]){
							l++;
						}
					}
					while(k < len-1 && nums[k] == nums[k+1]){
						k++;
					}
				}
				// cout << "origin j:" << j << endl;
				while(j < len-1 && nums[j] == nums[j+1]){
					j++;
					// cout << "plus j:" << j << endl;
				}
			}
			while(i < len-1 && nums[i] == nums[i+1]){
				i++;
			}
		}
		return res;
	}
	
	// 双指针 -2 -1 0 0 1 2
	vector<vector<int>> fourSum2(vector<int>& nums, int target){
		int len = nums.size();
		vector<vector<int>> res;
		if(len < 4){
			return {};
		}
		sort(nums.begin(), nums.end());
		// for(auto num : nums){
			// cout << num << " ";
		// }
		// cout << endl;
		if((long)nums[len-4] + nums[len-3] + nums[len-2] + nums[len-1] < target){
			return res;
		}
		for(int i = 0; i < len - 3; i++){
			cout << "i:" << i << endl;
			if((long)nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target){
				return res;
			}
			for(int j = i + 1; j < len - 2; j++){
				if((long)nums[i] + nums[len-3] + nums[len-2] + nums[len-1] < target){
					break;
				}
				if((long)nums[i] + nums[j] + nums[j+1] + nums[j+2] > target){
					break;
				}
				int left = j + 1;
				int right = len - 1;
				while(left < right){
					//cout << "nums[i]:" << nums[i] << "nums[j]:" <<  nums[j] << "left:" <<  nums[left] << "right:" << nums[right] << endl;
					//cout << "nums[i]:" << i << "nums[j]:" <<  j << "left:" <<  left << "right:" << right << endl;
					if((long)nums[i] + nums[j] + nums[left] + nums[right] == target){
						res.push_back({nums[i], nums[j], nums[left], nums[right]});
						while(left < len-1 && nums[left] == nums[left+1]){
							left++;
						}
						left++;
					}
					else if((long)nums[i] + nums[j] + nums[left] + nums[right] < target){
						left++;
					}
					else{
						right--;
					}
				}
				
				while(j < len-1 && nums[j] == nums[j+1]){
					j++;
				}
			}
			while(i < len-1 && nums[i] == nums[i+1]){
				i++;
			}
		}
		return res;
	}
	
	// height = 4
	void dfs(vector<int>& nums, int len, int target, int level, vector<int> combine, vector<vector<int>> & res, int sum, int fromI){
		if(level == 3){
			if(sum == target){
				res.push_back(combine);
			}
			return;
		}
		for(int i = fromI; i < len - 3; i++){
			sum += fromI;
			if(level == 2){
				if(sum > target){
					return;
				}
			}
			combine.push_back(i);
			dfs(nums, len, target, level++, combine, res, sum, i++);
		}
		
	}
	
};

int main(){
	Solution so;
	vector<int> input = {-2,-1,-1,1,1,2,2};
	int target = 0;
	vector<vector<int>> res = so.fourSum2(input, target);
	// cout << res.size() << endl;
	for(auto v : res){
		cout << "[" << v[0] << " " << v[1] << " " << v[2] << " " << v[3] << "]" << endl;
	}
	return 0;
}